//package com.lanqiao.binarysorttree;
//
//public class BinarySortTreeDemo {
//
//	public static void main(String[] args) {
//		int[] arr= {7, 3, 10, 12, 5, 1, 9, 0};
//		BinarySortTree binarySortTree = new BinarySortTree();
//		for (int i : arr) {
//			binarySortTree.add(new Node(i));
//		}
//		//System.out.println("中序遍历");
//		//binarySortTree.infixOrder();
//		binarySortTree.delNode(10);
//		binarySortTree.infixOrder();
//		
//	}
//
//}
//
//class BinarySortTree {
//	private Node root;
//	
//	
//	public Node search(int value) {
//		if (root == null) {
//			return null;
//		} else {
//			return root.search(value);
//		}
//	}
//	
//	public Node searchParent(int value) {
//		if (root == null) {
//			return null;
//		} else {
//			return root.searchParent(value);
//		}
//	}
//	
//	/**
//	 * 
//	 * @param node 传入节点（当作二叉排序树的根节点）
//	 * @return 返回以node为根节点的二叉排序树的最小结点的值
//	 */
//	public int delRightTreeMin(Node node) {
//		Node target = node;
//		//循环查找左节点，找到最小值
//		while (target.left != null) {
//			target = target.left;
//		}
//		//这时target指向最小结点
//		//因为要将其替换到targetNode删除的位置，所以该节点要删除
//		delNode(target.value);
//		return target.value;//返回最小结点的值，用于替换删除结点targetNode
//	}
//	
//	
//	public void delNode(int value) {
//		if (root == null) {
//			return;
//		} else {
//			//1. 先找到要删除的结点 targetNode
//			Node targetNode = search(value);
//			//没有找到
//			if (targetNode == null) {
//				return;
//			}
//			//找到了，且该数只有一个结点
//			if (root.left == null && root.right == null) {
//				root = null;
//				return;
//			}
//			//找到targetNode的父节点
//			Node parent = searchParent(value);
//			//（一） 如果要删除的结点是叶子节点
//			if (targetNode.left == null && targetNode.right == null) {
//				//判断targetNode是parent的左，还是右
//				if (parent.left != null && parent.left.value == value) {//左子节点
//					parent.left = null;
//				} else if (parent.right != null && parent.right.value == value) {//右子节点
//					parent.right = null;
//				}
//			} else if (targetNode.left != null && targetNode.right != null) {//（二） 删除有两颗子树的结点
//				//右子树寻找最小结点替换
//				targetNode.value = delRightTreeMin(targetNode.right);
//				
//			} else {//（三） 删除有一颗子树的结点
//				//如果要删除的结点有左子节点
//				if (targetNode.left != null) {
//					if (parent != null) {
//						// targetNode是parent的左子节点
//						if (parent.left.value == value) {
//							parent.left = targetNode.left;
//						} else {
//							parent.right = targetNode.left;
//						}
//					} else {//若该节点为root，且只有一个子节点
//						root = targetNode.left;
//					}
//				} else {//如果要删除的结点有右子节点
//					if (parent != null) {
//						// targetNode是parent的左子节点
//						if (parent.left.value == value) {
//							parent.left = targetNode.right;
//						} else {
//							parent.right = targetNode.right;
//						}
//					} else {
//						root = targetNode.right;
//					}
//				}
//			}
//			
//		}
//	}
//	
//	public void add(Node node) {
//		if (root == null) {
//			root = node;
//		} else {
//			root.add(node);
//		}
//	}
//	
//	public void infixOrder() {
//		if (root != null) {
//			root.infixOrder();
//		} else {
//			System.out.println("null!");
//		}
//	}
//	
//	
// }
//
//
//class Node {
//	int value;
//	Node left;
//	Node right;
//	
//	public Node(int value) {
//		
//		this.value = value;
//	}
//	
//	//添加结点,需要满足二叉排序树的要求
//	//递归方式
//	public void add(Node node) {
//		if (node == null) {
//			return;
//		}
//		//判断传入结点的值
//		if (node.value < this.value) {
//			//当前节点的左为空
//			if (this.left == null) {
//				 this.left = node;
//			} else {
//				//递归向左
//				this.left.add(node);
//			}
//		} else {
//			if (this.right == null) {
//				this.right = node;
//			} else {
//				this.right.add(node);
//			}
//		}
//	}
//	
//	public void infixOrder() {
//		if (this.left != null) {
//			this.left.infixOrder();
//		}
//		System.out.println(this);
//		if (this.right != null) {
//			this.right.infixOrder();
//		}
//	}
//	
//	//查找结点的值为value
//	public Node search(int value) {
//		if (value == this.value) {
//			return this;
//		} else if (value < this.value) {
//			if (this.left == null) {
//				return null;
//			}
//			return this.left.search(value);
//		} else {
//			if (this.right == null) {
//				return null;
//			}
//			return this.right.search(value);
//		}
//	}
//	
//	//查找该节点的父节点，在删除操作时需要使用
//	public Node searchParent(int value) {
//		if (this.left != null && this.left.value == value || 
//				this.right != null && this.right.value == value) {
//			return this;
//		} else {
//			if (value < this.value && this.left != null) {
//				return this.left.searchParent(value);
//			} else if (value >= this.value && this.right != null) {
//				return this.right.searchParent(value);
//			} else {
//				return null;//没有父节点
//			}
//		}
//	}
//
//	@Override
//	public String toString() {
//		return "Node [value=" + value + "]";
//	}
//	
//}
//
//
